<?php

function seq2tree(array $sequence)
{
    $tree = [];
    $offset = 0;
    $nodeNumber = count($sequence);
    $layerNumber = (int) ceil(log($nodeNumber + 1, 2));
    for ($i = 0; $i < $layerNumber; $i++) {
        $layer = [];
        $l = pow(2, $i);
        if ($offset + $l <= $nodeNumber) {
            for ($j = 0; $j < $l; $j++) {
                $layer[] = $sequence[$offset + $j];
            }
            $offset += $l;
        } else {
            $layer = array_slice($sequence, $offset);
        }

        $tree[] = $layer;
    }

    return $tree;
}

function tree2seq(array $tree)
{
    $seq = [];
    foreach ($tree as $layer) {
        $seq = array_merge($seq, $layer);
    }

    return $seq;
}

function transFunc($seq, $x)
{
    $tree = seq2tree($seq);
    $l = count($tree);

    // 输入补成完美树
    $res = array_pad([], pow(2, $l), $x);
    // 从下向上依次计算
    for ($i = $l - 1; $i >= 0; $i--) {
        $tmp = array_pad([], pow(2, $i), $x);
        $vec = $tree[$i];
        $llen = count($vec);
        for ($j = 0; $j < $llen; $j++) {
            $tmp[$j] = $vec[$j]($res[2 * $j], $res[2 * $j + 1]);
        }
        $res = $tmp;
    }

    return $res[0];
}
